A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the patent and trademark office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates to memory management schemes for use in data communications, specifically packet routing.
2. Description of the Related Art
In routing of a packet in a modem data communication system, one of the many tasks to accomplish is to determine the longest Internet Protocol (IP) prefix match for a destination address derived from the packet header. Many systems exist for determining such matches, both in the context of Internet Protocol routing as well as other forms of routing and switching (such as those employed with the asynchronous transfer mode (ATM) communications). See for example, U.S. Pat. No. 5,809,501 to Noven, entitled Method and System of Database Management and an Asynchronous Transfer Mode (ATM) Environment and U.S. Pat. No. 5,884,297 also to Noven, entitled System and Method for Maintaining a Table in Content Addressable Memory Using Hole Algorithms. Both of these patents are incorporated herein by reference in their entireties.
Within routers and switches today, the process whereby the routing function is carried out is well known in the art. Part of that process is the step of determining whether or not a router is aware of the corresponding next hop destination for packet routing. This typically uses a lookup of certain elements of the packet or cell header in a table to determine packet routing. Ternary content addressable memory (TCAM) is a type of memory that supports such lookups, and in particular the longest binary prefix lookup commonly used in routers.
As is well-known in the art, a content addressable memory (CAM) lookup outputs an exact match: either the parameter to be looked up (i.e., the lookup key) is in the CAM table or it is not. If the key is found in the table, an exact match exists and the address in the CAM table where the entry was found is provided as the output of the lookup. TCAMs differ from CAMs in that a TCAM allows the user to mask off bits such that a lookup key is said to match a TCAM entry even if all bits in the key do not match the entry. In other words, by masking out certain bits in the TCAM as xe2x80x9cdon""t carexe2x80x9d bits, more than one lookup key can be said to match a TCAM entry. If several TCAM entries match the lookup key, the top-most one (i.e., the entry having the lowest address) is returned. This feature is useful in supporting the longest IP prefix lookup function because the object of the search is only to find the longest prefix match, not to find all exact matches.
Longest prefix lookups are commonly implemented using a TCAM by placing the prefix entries in descending order sorted by the length of prefix. FIG. 1 illustrates a prior art TCAM-implemented lookup table 100 containing these sorted prefix entries 110. The non-prefix bits of the IP address in the TCAM are masked off; the masked bits 150 are illustrated by dark cross-hatching. For Internet Protocol version 4 (IPv4), the IP addresses are 32 bits long: sorting these addresses into a TCAM thus creates a table having 32 different regions, where each region 1 consists of prefix entries of a length i, i being the number of unique bits in an entry.
FIG. 1 shows a representative prior art TCAM containing prefix entries 110 and holes 120. Regions 1 are further identified each from the others by the number of unique prefix bits contained therein: region 1-32 is 32 unique bits wide; region 1-31 is 31 bits (with the low order bit 1 masked off by the TCAM); and so on through region 1-1, which has the 31 low-order bits masked off. For example, entry 110-29 is in prefix region 1-29 and has 29 unique prefix bits and 3 bits masked off as xe2x80x9cdon""t carexe2x80x9d 150.
The lowest address entry is 110-32, in the 32-bit prefix region 1-32. The highest entry (in the bottom-most position) in TCAM table 100 is hole 120 in region 1-1.
FIG. 1 is only a representative illustration of a portion of a TCAM configured for longest prefix match lookups. One of ordinary skill in the art will readily understand that TCAMs of widths greater than 32 bits are commonly used and that the length (xe2x80x9cdepthxe2x80x9d) of the TCAM can vary.
In operation, lookup key 105 is compared to every entry 110 in TCAM 100. Note that hole 120 is not necessarily all zeros; in some embodiments of the present invention, the contents of a single bit (or a field having a plurality of bits) in the unmasked portion of the entry 110 signals that the entry is in fact a hole 120. The comparison of key 105 to all entries in TCAM 100 is done simultaneously by a bit-wise NOT(XOR) with every unmasked bit in every entry. If an AND function of the results of all of the NOT(XOR) operations for an entry 110 is TRUE, the all bits of that entry 110 match key 105. The address of the lowest-addressed (and therefore longest prefix) entry is provided to the TCAM output.
Note that in the upcoming standard Internet Protocol version 6 (IPv6), the IP address is 128 bits. IPv6 will thus necessitate a TCAM having 128 distinct IP prefix length regions.
Although the ability of the TCAM to rapidly produce longest prefix lookup matches is advantageous, it complicates the task of inserting and deleting new prefixes within the TCAM table. This is so because the TCAM table must be maintained in a prefix length sorted order. Though TCAM updates (inserts and deletes) are infrequent, a time consuming update mechanism steals valuable processor resources and potentially result in a dropping of packets. Such deleterious effects must be avoided if high packet switching/routing speeds are to be maintained. The problem is only exacerbated by the expected industry switch to the lPv6 architecture with its longer addresses.
An insert of a prefix of length i can be accomplished in one TCAM write cycle if there is a vacant entry in the ith region (e.g., hole 120 in region 1-32), otherwise the TCAM write may need to move a vacant entry from a neighboring region (e.g., region 1-31) in order to provide space in the ith region. In particular, if up to k regions on either side of the ith region have no vacant entries, then one would need to perform k moves to provide a space. Since the cost of a move (involving both reading and writing the entry) is much higher than that of a lookup, it is desirable to minimize the number of moves involved in TCAM updates.
In one prior art method commonly used, a xe2x80x9cnaivexe2x80x9d algorithm for TCAM updates is employed. The naive (or xe2x80x9clazyxe2x80x9d) algorithm moves TCAM entries only when it needs to. A delete in a given region 1 creates a hole 120 in that region.
Conversely, an insert in a region 1 requires the presence of a hole 120 in that region in which to insert the entry. A region is referred to as a xe2x80x9cfullxe2x80x9d region when it does not have any holes (e.g., region 1-30), and thus an insert into a full region requires moving a hole 120 into that region from the nearest non-full region 1. This may necessitate moving entries in adjoining regions as well, in order to make room. It is desirable that the number of moves required to supply a hole to a full region is minimized. Indeed, it is preferable to have some holes in each region to facilitate updating.
Consider a TCAM with a certain maximum number of entries. One can readily see that some routing applications could use enough IP prefixes to result in a TCAM occupancy rate of 90% or more. In fact, such occupancy rates are commonly seen in the art today. A 90% occupancy rate implies that 10% of the TCAM entries are holes. A xe2x80x9cgood distributionxe2x80x9d of these holes is one where they are almost equally distributed among the 32 regions (in an Pv4 system) so that one does not encounter a full region during any insert. Obviously, a xe2x80x9cbad distributionxe2x80x9d is one where several full regions occur contiguously, resulting in the requirement for a number of moves in order to provide a hole to support an insertion.
A good TCAM update algorithm will thus try to ensure that if one starts with a good distribution of holes among the regions, then after several updates the hole distribution will remain good. The naeve algorithm unfortunately gets stuck in a bad distribution once it reaches that state and never recovers on its own. If k full regions occur contiguously at any point, then the naive algorithm incurs an average cost of k/2 moves for every future insert into one of those regions. For example, if the lowest-addressed one third of the prefix regions in the TCAM increase in size by 10%, they will borrow holes from the middle third. This can result in a complete lack of holes in the middle region, which is too large for a naive algorithm to compensate. This cost results in a packet processing delay, which can in turn cause packet drops.
A study of the problem has indicated that a good TCAM update algorithm has the following desirable properties:
Given a good distribution of holes among regions, the distribution should tend to remain good after several updates.
Even if the TCAM is forced into a bad distribution, the update algorithm should automatically recover to a good distribution with future updates.
These properties can be achieved by performing a single (or a few) smart, proactive moves with every TCAM insert. These extra moves are performed to obtain and maintain an equal hole distribution among regions.
Another basic problem with the prior art naive algorithm is that, even if there are holes within a region available for insert, one still needs to search for them, again incurring undesirable delays. Because these holes may be scattered throughout the region, finding one can become an expensive task in terms of processor resources. There are presently two approaches commonly used in such situations.
1. Go through the entire region looking for available holes. This method is time consuming and thus could lead to packet drops.
2. Maintain a doubly-linked list of holes for each region and use that data structures to locate a hole. Though this approach allows us to locate a hole in a constant amount of time (independent of the size of the region, number of holes, and the number of regions,a period represented in algorithmic analysis literature as order-1 or xe2x80x9cO(1)xe2x80x9d time complexity), it requires maintaining complicated data structures in the TCAM controller. Any hardware or firmware implementation of the TCAM controller would thus consume additional (and scarce) memory and code space resources.
What is needed is an efficient algorithm for TCAM updates that establishes a good distribution of holes among regions, maintains that good distribution over multiple inserts and deletions, and provides a rapid method for locating and utilizing holes in a given region.
Presently disclosed are techniques for efficient memory management that enable rapid longest prefix match in TCAMs. The present invention is equally applicable to other types of memory besides TCAMs, as well as for memory lookup schemes other than those used for longest prefix match. In general, the present invention is efficacious wherever maintenance of a good distribution of holes in a sorted list is required. This technique relies on a proactive hole management methodology to preserve a good distribution of holes in each TCAM region in such a way that one does not have to search for them in order to effect an insertion. In particular, all holes in a given region are kept in one or more contiguous sub-regions. Keeping the holes contiguous requires a hole move every time there is a delete operation. The amortized cost of these operations is justified by the resulting simplification in later insert and delete operations. For example, during an insert the new entry is stored at either end of the contiguous section of used entries in the region. During a delete, when a hole is created in the middle of a contiguous sub-region of used entries, the last used entry is moved into the hole, thus keeping the holes contiguous. Such an organization of holes and movement of used entries within a region is permissible within the longest prefix match type of lookup table, because all entries within a region, by definition, have an IP prefix of equal length.